Реализовать стек с использованием двух очередей

Question

Аналогичный вопрос задавался ранее there, но вопрос здесь обратный, используя две очереди в виде стека. Вопрос ...

Учитывая две очереди с их стандартными операциями (enqueue, dequeue, isempty, size), реализовать стек с его стандартными операциями (pop, push, isempty, size).

Должно быть вариантов решения.

• Версия : Стек должен быть эффективен при нажатии элемента; и
• Версия B: Стек должен быть эффективным при появлении элемента.

Меня интересует алгоритм больше, чем любые конкретные языковые реализации. Тем не менее, я приветствую решения, выраженные на известных мне языках (java, c#, python, vb, javascript, php).

Answer 1

Вариант А (эффективное нажатие):

• толчок:
  • Enqueue в queue1
• поп:
  • в то время как размер queue1 больше, чем 1, трубы выгруженные объекты из очереди1 в очередь2
  • Dequeue и вернуть последний элемент queue1, затем переключить имена queue1 и queue2

Version B (эффективная поп):

• нажимной:
  • Ставить в queue2
  • введите все элементы queue1 в queue2, затем переключите имена queue1 и queue2
• поп:
  • deqeue из queue1

Answer 2

Самый простой (и, возможно, единственный) способ сделать это, нажав новые элементы в пустой очереди, а затем извлечение из другого и enqeuing в ранее пустую очередь. Таким образом, последняя всегда находится в передней части очереди. Это будет версия B, для версии A вы просто меняете процесс, отбрасывая элементы во вторую очередь, за исключением последней.

Шаг 0:

"Stack" 
+---+---+---+---+---+ 
| | | | | | 
+---+---+---+---+---+ 

Queue A    Queue B 
+---+---+---+---+---+ +---+---+---+---+---+ 
| | | | | | | | | | | | 
+---+---+---+---+---+ +---+---+---+---+---+ 

Шаг 1:

"Stack" 
+---+---+---+---+---+ 
| 1 | | | | | 
+---+---+---+---+---+ 

Queue A    Queue B 
+---+---+---+---+---+ +---+---+---+---+---+ 
| 1 | | | | | | | | | | | 
+---+---+---+---+---+ +---+---+---+---+---+ 

Шаг 2:

"Stack" 
+---+---+---+---+---+ 
| 2 | 1 | | | | 
+---+---+---+---+---+ 

Queue A    Queue B 
+---+---+---+---+---+ +---+---+---+---+---+ 
| | | | | | | 2 | 1 | | | | 
+---+---+---+---+---+ +---+---+---+---+---+ 

Шаг 3:

"Stack" 
+---+---+---+---+---+ 
| 3 | 2 | 1 | | | 
+---+---+---+---+---+ 

Queue A    Queue B 
+---+---+---+---+---+ +---+---+---+---+---+ 
| 3 | 2 | 1 | | | | | | | | | 
+---+---+---+---+---+ +---+---+---+---+---+ 

Answer 3

Вот мой ответ - где «поп» неэффективен. Кажется, что все алгоритмы, которые сразу приходят в голову, имеют N сложности, где N - размер списка: выбираете ли вы работу над «попсом» или выполняете работу над «push»

Алгоритм, в котором перечислены торгуются обратно, а четвертый может быть лучше, в качестве расчета размера не требуется, хотя вам все равно нужно зацикливать и сравнить с пустым.

Вы можете доказать, что этот алгоритм нельзя записать быстрее, чем N, отметив, что информация о последнем элементе в очереди доступна только через знание размера очереди и что вы должны уничтожить данные, чтобы добраться до этого элемента, следовательно, вторая очередь.

Единственный способ сделать это быстрее - не использовать очереди в первую очередь.

from data_structures import queue 

class stack(object): 
    def __init__(self): 
     q1= queue 
     q2= queue #only contains one item at most. a temp var. (bad?) 

    def push(self, item): 
     q1.enque(item) #just stick it in the first queue. 

    #Pop is inefficient 
    def pop(self): 
     #'spin' the queues until q1 is ready to pop the right value. 
     for N 0 to self.size-1 
      q2.enqueue(q1.dequeue) 
      q1.enqueue(q2.dequeue) 
     return q1.dequeue() 

    @property 
    def size(self): 
     return q1.size + q2.size 

    @property 
    def isempty(self): 
     if self.size > 0: 
      return True 
     else 
      return False 

Answer 4

import java.util.*; 

/** 
* 
* @author Mahmood 
*/ 
public class StackImplUsingQueues { 

    Queue<Integer> q1 = new LinkedList<Integer>(); 
    Queue<Integer> q2 = new LinkedList<Integer>(); 

    public int pop() { 
     if (q1.peek() == null) { 
      System.out.println("The stack is empty, nothing to return"); 
      int i = 0; 
      return i; 
     } else { 
      int pop = q1.remove(); 
      return pop; 
     } 
    } 

    public void push(int data) { 

     if (q1.peek() == null) { 
      q1.add(data); 
     } else { 
      for (int i = q1.size(); i > 0; i--) { 
       q2.add(q1.remove()); 
      } 
      q1.add(data); 
      for (int j = q2.size(); j > 0; j--) { 
       q1.add(q2.remove()); 
      } 

     } 
    } 

    public static void main(String[] args) { 
     StackImplUsingQueues s1 = new StackImplUsingQueues(); 
     //  Stack s1 = new Stack(); 
     s1.push(1); 
     s1.push(2); 
     s1.push(3); 
     s1.push(4); 
     s1.push(5); 
     s1.push(6); 
     s1.push(7); 
     s1.push(8); 
     s1.push(9); 
     s1.push(10); 
     // s1.push(6); 
     System.out.println("1st = " + s1.pop()); 
     System.out.println("2nd = " + s1.pop()); 
     System.out.println("3rd = " + s1.pop()); 
     System.out.println("4th = " + s1.pop()); 
     System.out.println("5th = " + s1.pop()); 
     System.out.println("6th = " + s1.pop()); 
     System.out.println("7th = " + s1.pop()); 
     System.out.println("8th = " + s1.pop()); 
     System.out.println("9th = " + s1.pop()); 
     System.out.println("10th= " + s1.pop()); 
    } 
} 

Answer 5

Как уже было сказано, не одна очередь сделать трюк? Это, вероятно, менее практично, но немного сглаживается.

push(x): 
enqueue(x) 
for(queueSize - 1) 
    enqueue(dequeue()) 

pop(x): 
dequeue() 

Answer 6

queue<int> q1, q2; 
int i = 0; 

void push(int v) { 
    if(q1.empty() && q2.empty()) { 
    q1.push(v); 
    i = 0; 
    } 
    else { 
    if(i == 0) { 
     while(!q1.empty()) q2.push(q1.pop()); 
     q1.push(v); 
     i = 1-i; 
    } 
    else { 
     while(!q2.empty()) q1.push(q2.pop()); 
     q2.push(v); 
     i = 1-i; 
    } 
    } 
} 

int pop() { 
    if(q1.empty() && q2.empty()) return -1; 
    if(i == 1) { 
     if(!q1.empty()) 
      return q1.pop(); 
     else if(!q2.empty()) 
      return q2.pop(); 
    } 
    else { 
     if(!q2.empty()) 
      return q2.pop(); 
     else if(!q1.empty()) 
      return q1.pop(); 
    } 
} 

Answer 7

Можем ли мы использовать только одну очередь, чтобы реализовать стек? Я могу использовать две очереди, но рассмотрение одной очереди будет более эффективным. Вот код:

public void Push(T val) 
    { 
     queLower.Enqueue(val); 
    } 

    public T Pop() 
    { 

     if (queLower.Count == 0) 
     { 
      Console.Write("Stack is empty!"); 
      return default(T); 

     } 
     if (queLower.Count > 0) 
     { 
      for (int i = 0; i < queLower.Count - 1;i++) 
      { 
       queLower.Enqueue(queLower.Dequeue()); 
      } 
        } 

     return queLower.Dequeue(); 

    } 

Answer 8

Мы можем сделать это с помощью одной очереди:

толчок:

1. Ставить новый элемент.
2. Если n - количество элементов в очереди, то удалите и вставьте элемент n-1 раз.

поп:

1. Dequeue

.Реализация

push 1 


front      
+----+----+----+----+----+----+ 
| 1 | | | | | | insert 1 
+----+----+----+----+----+----+ 


push2 

front      
+----+----+----+----+----+----+ 
| 1 | 2 | | | | | insert 2 
+----+----+----+----+----+----+ 

    front      
+----+----+----+----+----+----+ 
| | 2 | 1 | | | | remove and insert 1 
+----+----+----+----+----+----+ 




insert 3 


     front      
+----+----+----+----+----+----+ 
| | 2 | 1 | 3 | | | insert 3 
+----+----+----+----+----+----+ 

      front      
+----+----+----+----+----+----+ 
| | | 1 | 3 | 2 | | remove and insert 2 
+----+----+----+----+----+----+ 

       front      
+----+----+----+----+----+----+ 
| | | | 3 | 2 | 1 | remove and insert 1 
+----+----+----+----+----+----+ 

Пример:

int stack_pop (queue_data *q) 
{ 
    return queue_remove (q); 
} 

void stack_push (queue_data *q, int val) 
{ 
    int old_count = queue_get_element_count (q), i; 

    queue_insert (q, val); 
    for (i=0; i<old_count; i++) 
    { 
    queue_insert (q, queue_remove (q)); 
    } 
} 

Answer 9

Вот еще одно решение:

для PUSH: -Добавить первый элемент в очереди 1. -При добавления второго элемента и так далее, Enqueue сначала элемент в очереди 2, а затем скопируйте весь элемент из очереди 1 в очередь2. - для POP просто вычеркните элемент из очереди из вас, вставив последний элемент.

Так,

public void push(int data){ 
if (queue1.isEmpty()){ 
    queue1.enqueue(data); 
} else { 
queue2.enqueue(data); 
while(!queue1.isEmpty()) 
Queue2.enqueue(queue1.dequeue()); 
//EXCHANGE THE NAMES OF QUEUE 1 and QUEUE2 

}}

public int pop(){ 
int popItem=queue2.dequeue(); 
return popItem; 
}' 

Существует одна проблема, я не могу понять, как переименовать очереди ???

Answer 10

Вот мое решение, которое работает для O (1) в среднем случае. Есть две очереди: in и out. См псевдокод ниже:

PUSH(X) = in.enqueue(X) 

POP: X = 
    if (out.isEmpty and !in.isEmpty) 
    DUMP(in, out) 
    return out.dequeue 

DUMP(A, B) = 
    if (!A.isEmpty) 
    x = A.dequeue() 
    DUMP(A, B) 
    B.enqueue(x) 

Answer 11

Вот некоторые простые псевдо-код, толчок О (п), поп/PEEK представляет собой О (1):

Qpush = Qinstance() 
Qpop = Qinstance() 

def stack.push(item): 
    Qpush.add(item) 
    while Qpop.peek() != null: //transfer Qpop into Qpush 
     Qpush.add(Qpop.remove()) 
    swap = Qpush 
    Qpush = Qpop 
    Qpop = swap 

def stack.pop(): 
    return Qpop.remove() 

def stack.peek(): 
    return Qpop.peek() 

Answer 12

Пусть S1 и S2 две стеки использоваться при реализации очередей.

struct Stack 
{ struct Queue *Q1; 
    struct Queue *Q2; 
} 

Мы следим за тем, чтобы одна очередь была пустой.

Push operation: Независимо от того, какая очередь не пуста, вставьте в нее элемент.

• Проверьте, нет ли очереди Q1 или нет. Если Q1 пуст, то Enqueue элемент в нем.
• В противном случае EnQueue элемент в Q1.

Push (struct Stack *S, int data) { if(isEmptyQueue(S->Q1) EnQueue(S->Q2, data); else EnQueue(S->Q1, data); }

Время Сложность: O (1)

Поп Операция: Передача N-1 элементов в другой очереди и удаление последней из очереди для выполнения операции поп.

• Если очередь Q1 не пуста, передайте n-1 элементы из Q1 в Q2, а затем, DeQueue - последний элемент Q1 и верните его.
• Если очередь Q2 не пуста, передайте n-1 элементов из Q2 в Q1, а затем, DeQueue последний элемент Q2 и верните его.

`

int Pop(struct Stack *S){ 
int i, size; 
if(IsEmptyQueue(S->Q2)) 
{ 
size=size(S->Q1); 
i=0; 
while(i<size-1) 
{ EnQueue(S->Q2, Dequeue(S->Q1)) ; 
    i++; 
} 
return DeQueue(S->Q1); 
} 
else{ 
size=size(S->Q2); 
while(i<size-1) 
EnQueue(S->Q1, Dequeue(S->Q2)) ; 
i++; 
} 
return DeQueue(S->Q2); 
} } 

Время Сложность: Время выполнения поп операции представляет собой О (п), как каждый раз, когда поп называется, мы передача всех элементов из одной очереди в OTER.

Answer 13

#include <bits/stdc++.h> 
using namespace std; 
queue<int>Q; 
stack<int>Stk; 
void PRINT(stack<int>ss , queue<int>qq) { 
    while(ss.size()) { 
     cout << ss.top() << " " ; 
     ss.pop(); 
    } 
    puts(""); 
    while(qq.size()) { 
     cout << qq.front() << " " ; 
     qq.pop(); 
    } 
    puts("\n----------------------------------"); 
} 
void POP() { 
    queue<int>Tmp ; 
    while(Q.size() > 1) { 
     Tmp.push(Q.front() ); 
     Q.pop(); 
    } 
    cout << Q.front() << " " << Stk.top() << endl; 
    Q.pop() , Stk.pop() ; 
    Q = Tmp ; 
} 
void PUSH(int x) { 
    Q.push(x); 
    Stk.push(x); 
} 
int main() { 
    while(true) { 
     string typ ; 
     cin >> typ ; 
     if(typ == "push") { 
      int x ; 
      cin >> x; 
      PUSH(x); 
     } else POP(); 
     PRINT(Stk,Q); 
    } 
} 

Answer 14

Вот мое решение ..

Concept_Behind :: push(struct Stack* S,int data) :: Эта функция епдиеей первый элемент в Q1 и Q2 в остальных pop(struct Stack* S) :: если Q2 не опустошить переносит все Эль лет в Q1 и вернуть последний эль в Q2 еще (что означает Q2 пусто) передает весь Эль-й в Q2 и возвращает последний эль в Q1

Efficiency_Behind :: push(struct Stack*S,int data) :: O (1) // с одной Ставить на данные pop(struct Stack* S) :: O (n) // поскольку транслирует худшие n-1 данные за поп.

#include<stdio.h> 
#include<stdlib.h> 
struct Queue{ 
    int front; 
    int rear; 
    int *arr; 
    int size; 
    }; 
struct Stack { 
    struct Queue *Q1; 
    struct Queue *Q2; 
    }; 
struct Queue* Qconstructor(int capacity) 
{ 
    struct Queue *Q=malloc(sizeof(struct Queue)); 
    Q->front=Q->rear=-1; 
    Q->size=capacity; 
    Q->arr=malloc(Q->size*sizeof(int)); 
    return Q; 
    } 
int isEmptyQueue(struct Queue *Q) 
{ 
    return (Q->front==-1); 
    } 
int isFullQueue(struct Queue *Q) 
{ 
    return ((Q->rear+1) % Q->size ==Q->front); 
    } 
void enqueue(struct Queue *Q,int data) 
{ 
    if(isFullQueue(Q)) 
     { 
      printf("Queue overflow\n"); 
      return;} 
    Q->rear=Q->rear+1 % Q->size; 
    Q->arr[Q->rear]=data; 
    if(Q->front==-1) 
     Q->front=Q->rear; 
     } 
int dequeue(struct Queue *Q) 
{ 
    if(isEmptyQueue(Q)){ 
     printf("Queue underflow\n"); 
     return; 
     } 
    int data=Q->arr[Q->front]; 
    if(Q->front==Q->rear) 
     Q->front=-1; 
    else 
    Q->front=Q->front+1 % Q->size; 
    return data; 
    } 
///////////////////////*************main algo****************//////////////////////// 
struct Stack* Sconstructor(int capacity) 
{ 
    struct Stack *S=malloc(sizeof(struct Stack)); 
    S->Q1=Qconstructor(capacity); 
    S->Q2=Qconstructor(capacity); 
    return S; 
} 
void push(struct Stack *S,int data) 
{ 
    if(isEmptyQueue(S->Q1)) 
     enqueue(S->Q1,data); 
    else 
     enqueue(S->Q2,data); 
    } 
int pop(struct Stack *S) 
{ 
    int i,tmp; 
    if(!isEmptyQueue(S->Q2)){ 
     for(i=S->Q2->front;i<=S->Q2->rear;i++){ 
      tmp=dequeue(S->Q2); 
      if(isEmptyQueue(S->Q2)) 
       return tmp; 
      else 
       enqueue(S->Q1,tmp); 
       } 
      } 
    else{ 
     for(i=S->Q1->front;i<=S->Q1->rear;i++){ 
      tmp=dequeue(S->Q1); 
      if(isEmptyQueue(S->Q1)) 
       return tmp; 
      else 
       enqueue(S->Q2,tmp); 
       } 
      } 
     } 
////////////////*************end of main algo my algo************ 
///////////////*************push() O(1);;;;pop() O(n);;;;*******///// 
main() 
{ 
    int size; 
    printf("Enter the number of elements in the Stack(made of 2 queue's)::\n"); 
    scanf("%d",&size); 
    struct Stack *S=Sconstructor(size); 
    push(S,1); 
    push(S,2); 
    push(S,3); 
    push(S,4); 
    printf("%d\n",pop(S)); 
    push(S,5); 
    printf("%d\n",pop(S)); 
    printf("%d\n",pop(S)); 
    printf("%d\n",pop(S)); 
    printf("%d\n",pop(S)); 
    } 

Answer 15

import java.util.LinkedList; 
import java.util.Queue; 


public class StackQueue { 

    static Queue<Integer> Q1 = new LinkedList<Integer>(); 
    static Queue<Integer> Q2 = new LinkedList<Integer>(); 
    public static void main(String args[]) { 



     push(24); 
     push(34); 
     push(4); 
     push(10); 
     push(1); 
     push(43); 
     push(21); 
     System.out.println("Popped element is "+pop()); 
     System.out.println("Popped element is "+pop()); 
     System.out.println("Popped element is "+pop()); 


    } 

    public static void push(int data) { 

     Q1.add(data); 

    } 

    public static int pop() { 

     if(Q1.isEmpty()) { 
     System.out.println("Cannot pop elements , Stack is Empty !!"); 
     return -1; 
     } 
     else 
     { 
     while(Q1.size() > 1) { 
      Q2.add(Q1.remove()); 
     } 
     int element = Q1.remove(); 
     Queue<Integer> temp = new LinkedList<Integer>(); 
     temp = Q1; 
     Q1 = Q2; 
     Q2 = temp; 
     return element; 
     } 
    } 
} 

Answer 16

#include "stdio.h" 
#include "stdlib.h" 

typedef struct { 
    int *q; 
    int size; 
    int front; 
    int rear; 
} Queue; 
typedef struct { 
    Queue *q1; 
    Queue *q2; 
} Stack; 

int queueIsEmpty(Queue *q) { 
    if (q->front == -1 && q->rear == -1) { 
     printf("\nQUEUE is EMPTY\n"); 
     return 1; 
    } 
    return 0; 
} 
int queueIsFull(Queue *q) { 
    if (q->rear == q->size-1) { 
     return 1; 
    } 
    return 0; 
} 
int queueTop(Queue *q) { 
    if (queueIsEmpty(q)) { 
     return -1; 
    } 
    return q->q[q->front]; 
} 
int queuePop(Queue *q) { 
    if (queueIsEmpty(q)) { 
     return -1; 
    } 
    int item = q->q[q->front]; 
    if (q->front == q->rear) { 
     q->front = q->rear = -1; 
    } 
    else { 
     q->front++; 
    } 
    return item; 
} 
void queuePush(Queue *q, int val) { 
    if (queueIsFull(q)) { 
     printf("\nQUEUE is FULL\n"); 
     return; 
    } 
    if (queueIsEmpty(q)) { 
     q->front++; 
     q->rear++; 
    } else { 
     q->rear++; 
    } 
    q->q[q->rear] = val; 
} 
Queue *queueCreate(int maxSize) { 
    Queue *q = (Queue*)malloc(sizeof(Queue)); 
    q->front = q->rear = -1; 
    q->size = maxSize; 
    q->q = (int*)malloc(sizeof(int)*maxSize); 
    return q; 
} 
/* Create a stack */ 
void stackCreate(Stack *stack, int maxSize) { 
    Stack **s = (Stack**) stack; 
    *s = (Stack*)malloc(sizeof(Stack)); 
    (*s)->q1 = queueCreate(maxSize); 
    (*s)->q2 = queueCreate(maxSize); 
} 

/* Push element x onto stack */ 
void stackPush(Stack *stack, int element) { 
    Stack **s = (Stack**) stack; 
    queuePush((*s)->q2, element); 
    while (!queueIsEmpty((*s)->q1)) { 
     int item = queuePop((*s)->q1); 
     queuePush((*s)->q2, item); 
    } 
    Queue *tmp = (*s)->q1; 
    (*s)->q1 = (*s)->q2; 
    (*s)->q2 = tmp; 
} 

/* Removes the element on top of the stack */ 
void stackPop(Stack *stack) { 
    Stack **s = (Stack**) stack; 
    queuePop((*s)->q1); 
} 

/* Get the top element */ 
int stackTop(Stack *stack) { 
    Stack **s = (Stack**) stack; 
    if (!queueIsEmpty((*s)->q1)) { 
     return queueTop((*s)->q1); 
    } 
    return -1; 
} 

/* Return whether the stack is empty */ 
bool stackEmpty(Stack *stack) { 
    Stack **s = (Stack**) stack; 
    if (queueIsEmpty((*s)->q1)) { 
     return true; 
    } 
    return false; 
} 

/* Destroy the stack */ 
void stackDestroy(Stack *stack) { 
    Stack **s = (Stack**) stack; 
    free((*s)->q1); 
    free((*s)->q2); 
    free((*s)); 
} 

int main() 
{ 
    Stack *s = NULL; 
    stackCreate((Stack*)&s, 10); 
    stackPush((Stack*)&s, 44); 
    //stackPop((Stack*)&s); 
    printf("\n%d", stackTop((Stack*)&s)); 
    stackDestroy((Stack*)&s); 
    return 0; 
} 

Answer 17

Q1 = [10, 15, 20, 25, 30] 
Q2 = [] 

exp: 
{ 
    dequeue n-1 element from Q1 and enqueue into Q2: Q2 == [10, 15, 20, 25] 

    now Q1 dequeue gives "30" that inserted last and working as stack 
} 

swap Q1 and Q2 then GOTO exp 

Answer 18

import java.util.LinkedList; 
import java.util.Queue; 

class MyStack { 
    Queue<Integer> queue1 = new LinkedList<Integer>(); 
    Queue<Integer> queue2 = new LinkedList<Integer>(); 

    // Push element x onto stack. 
    public void push(int x) { 
     if(isEmpty()){ 
      queue1.offer(x); 
     }else{ 
      if(queue1.size()>0){ 
       queue2.offer(x); 
       int size = queue1.size(); 
       while(size>0){ 
        queue2.offer(queue1.poll()); 
        size--; 
       } 
      }else if(queue2.size()>0){ 
       queue1.offer(x); 
       int size = queue2.size(); 
       while(size>0){ 
        queue1.offer(queue2.poll()); 
        size--; 
       } 
      } 
     } 
    } 

    // Removes the element on top of the stack. 
    public void pop() { 
     if(queue1.size()>0){ 
      queue1.poll(); 
     }else if(queue2.size()>0){ 
      queue2.poll(); 
     } 
    } 

    // Get the top element. You can make it more perfect just example 
    public int top() { 
     if(queue1.size()>0){ 
      return queue1.peek(); 
     }else if(queue2.size()>0){ 
      return queue2.peek(); 
     } 
     return 0; 
    } 

    // Return whether the stack is empty. 
    public boolean isEmpty() { 
     return queue1.isEmpty() && queue2.isEmpty(); 
    } 
} 

Answer 19

Python код с помощью всего одной очереди

class Queue(object): 
    def __init__(self): 
     self.items=[] 
    def enqueue(self,item): 
     self.items.insert(0,item) 
    def dequeue(self): 
     if(not self.isEmpty()): 
      return self.items.pop() 
    def isEmpty(self): 
     return self.items==[] 
    def size(self): 
     return len(self.items) 



class stack(object): 
     def __init__(self): 
      self.q1= Queue() 


     def push(self, item): 
      self.q1.enqueue(item) 


     def pop(self): 
      c=self.q1.size() 
      while(c>1): 
       self.q1.enqueue(self.q1.dequeue()) 
       c-=1 
      return self.q1.dequeue() 



     def size(self): 
      return self.q1.size() 


     def isempty(self): 
      if self.size > 0: 
       return True 
      else: 
       return False 

Answer 20

здесь полный рабочего код в C#:

Он был реализован с одной очередью,

толчок:

1. add new element. 
2. Remove elements from Queue (totalsize-1) times and add back to the Queue 

поп:

normal remove 





using System; 
    using System.Collections.Generic; 
    using System.Linq; 
    using System.Text; 
    using System.Threading.Tasks; 

    namespace StackImplimentationUsingQueue 
    { 
     class Program 
     { 
      public class Node 
      { 
       public int data; 
       public Node link; 
      } 
      public class Queue 
      { 
       public Node rear; 
       public Node front; 
       public int size = 0; 
       public void EnQueue(int data) 
       { 
        Node n = new Node(); 
        n.data = data; 
        n.link = null; 
        if (rear == null) 
         front = rear = n; 
        else 
        { 
         rear.link = n; 
         rear = n; 
        } 
        size++; 
        Display(); 
       } 
       public Node DeQueue() 
       { 
        Node temp = new Node(); 
        if (front == null) 
         Console.WriteLine("Empty"); 
        else 
        { 
         temp = front; 
         front = front.link; 
         size--; 
        } 
        Display(); 
        return temp; 
       } 
       public void Display() 
       { 
        if (size == 0) 
         Console.WriteLine("Empty"); 
        else 
        { 
         Console.Clear(); 
         Node n = front; 
         while (n != null) 
         { 
          Console.WriteLine(n.data); 
          n = n.link; 
         } 
        } 
       } 
      } 
      public class Stack 
      { 
       public Queue q; 
       public int size = 0; 
       public Node top; 
       public Stack() 
       { 
        q = new Queue(); 
       } 
       public void Push(int data) 
       { 
        Node n = new Node(); 
        n.data = data; 
        q.EnQueue(data); 
        size++; 
        int counter = size; 
        while (counter > 1) 
        { 
         q.EnQueue(q.DeQueue().data); 
         counter--; 
        } 
       } 
       public void Pop() 
       { 
        q.DeQueue(); 
        size--; 
       } 
      } 
      static void Main(string[] args) 
      { 
       Stack s= new Stack(); 
       for (int i = 1; i <= 3; i++) 
        s.Push(i); 
       for (int i = 1; i < 3; i++) 
        s.Pop(); 
       Console.ReadKey(); 
      } 
     } 
    } 

Answer 21

Вот мой код в Java для реализации стека с использованием очередей.

import java.util.LinkedList; 
    import java.util.Queue; 

    /* 
    @Rishabh Sairawat 
    */ 
    public class StackImplementationiUsingQueue { 
    Queue<Integer> q1=new LinkedList<Integer>(); 
    Queue<Integer> q2=new LinkedList<Integer>(); 
    //push operation 
    public void push(int data){ 
    this.q1.add(data); 
    } 
    //pop operation 
    public int pop(){ 
    if(this.q1.isEmpty()){ 
     System.out.println("No Element found !"); 
    } 
    else { 
     int x; 
     while(this.q1.size()>1){ 
      x=this.q1.remove(); 
      this.q2.add(x); 
     } 
     x=q1.remove(); 
     this.q1.addAll(q2); 
     return x; 
    } 
    return -1; 
    } 
    public static void main(String[] args) { 
    StackImplementationiUsingQueue stack=new 
    StackImplementationiUsingQueue(); 
    stack.push(1); 
    stack.push(2); 
    stack.push(3); 
    stack.push(4); 
    stack.push(5); 
    System.out.println(stack.pop()); 
    System.out.println(stack.pop()); 
    System.out.println(stack.pop()); 
    System.out.println(stack.pop()); 
    System.out.println(stack.pop()); 
} 

}

Answer 22

Вот очень простое решение, которое использует один очереди и предоставляет функциональные возможности, как стек.

public class CustomStack<T> 
{ 
    Queue<T> que = new Queue<T>(); 

    public void push(T t) // STACK = LIFO/QUEUE = FIFO 
    { 

     if(que.Count == 0) 
     { 
      que.Enqueue(t); 
     } 
     else 
     { 
      que.Enqueue(t); 
      for (int i = 0; i < que.Count-1; i++) 
      { 
       var data = que.Dequeue(); 

       que.Enqueue(data); 
      } 
     } 

    } 

    public void pop() 
    { 

     Console.WriteLine("\nStack Implementation:"); 
     foreach (var item in que) 
     { 
      Console.Write("\n" + item.ToString() + "\t"); 
     } 

     var data = que.Dequeue(); 
     Console.Write("\n Dequeing :" + data); 
    } 

    public void top() 
    { 

     Console.Write("\n Top :" + que.Peek()); 
    } 


} 

Таким образом, в приведенном выше класс под названием «CustomStack», что я делаю, это просто проверка очереди на пустой, если пусто, то вставить одну и с тех пор в палатах вставки, а затем снимите вставку. По этой логике сначала наступит последняя. Пример: В очереди я вставил 1 и теперь пытаюсь вставить 2. Второй раз удалите 1 и снова вставьте, чтобы он стал в обратном порядке.

спасибо.