|
Data Structures Stack and Queue - August 22, 2008 at 13:10 PM by
Rajmeet Ghai
Describe stack operation.
Answer
Stack is a data structure that follows Last in First out strategy.
Stack Operations:-
-
Push – Pushes (inserts) the element in the stack. The location is specified by
the pointer.
-
Pop – Pulls (removes) the element out of the stack. The location is specified
by the pointer
-
Swap: - the two top most elements of the stack can be swapped
-
Peek: - Returns the top element on the stack but does not remove it from the
stack
-
Rotate:- the topmost (n) items can be moved on the stack in a rotating fashion
A stack has a fixed location in the memory. When a data element is pushed in the
stack, the pointer points to the current element.
Describe queue operation.
Answer
Queue is a data structure that follows First in First out strategy.
Queue Operations:
-
Push – Inserts the element in the queue at the end.
-
Pop – removes the element out of the queue from the front
-
Size – Returns the size of the queue
-
Front – Returns the first element of the queue.
-
Empty – to find if the queue is empty.
Discuss how to implement queue using stack.
Answer
A queue can be implemented by using 2 stacks:-
-
1. An element is inserted in the queue by pushing it into stack 1
-
2. An element is extracted from the queue by popping it from the stack 2
-
3. If the stack 2 is empty then all elements currently in stack 1 are
transferred to stack 2 but in the reverse order
-
4. If the stack 2 is not empty just pop the value from stack
2.
|