[TOC]
# stack an queue
## stack
- stack
- 都是重最上面拿走
- A stack is an ordered list in which insertions (or called additions or pushes) and deletions (or called removals or pops) are made at one end called the top.
- Last-In-First-Out (LIFO) order (後進先出)**change at same end**
### push
把data 加入序列
```C++
template < class T >
void Stack < T >::Push (const T& x)
{ // Add x to stack
if(top == capacity – 1)
{
ChangeSize1D(stack, capacity, 2*capacity);
capacity *= 2;
}
stack [ ++top ] = x;
}
```
### pop
把data 重序列刪除
``` c++
template < class T >
void Stack < T >::Pop ( )
{ // Delete top element from stack
if(IsEmpty()) throw “Stack is empty. Cannot delete.”;
stack [ top-- ].~T(); // Delete the element
}
```
### stack ADT
``` C++
template < class T >
class Stack // A finite ordered list
{
public:
// Constructor
Stack (int stackCapacity = 10);
// Check if the stack is empty
bool IsEmpty ( ) const;
// Return the top element
T& Top ( ) const;
// Insert a new element at top
void Push (const T& item);
// Delete one element from top
void Pop ( );
private:
T* stack;
int top; // init. value = -1
int capacity;
};
```
### Balanced parentheses
here is an i.e to use stack
step how we need to think
``` python
def areParanthesisBalanced(expr) :
stack = []
# Traversing the Expression
for char in expr:
if char in ["(", "{", "["]:
# Push the element in the stack
stack.append(char)
else:
# IF current character is not opening
# bracket, then it must be closing.
# So stack cannot be empty at this point.
if not stack:
return False
current_char = stack.pop()
if current_char == '(':
if char != ")":
return False
if current_char == '{':
if char != "}":
return False
if current_char == '[':
if char != "]":
return False
# Check Empty Stack
if stack:
return False
return True
# Driver Code
if __name__ == "__main__" :
expr = "{()}[]";
if areParanthesisBalanced(expr) :
print("Balanced");
else :
print("Not Balanced");
# This code is contributed by AnkitRai01 and improved
# by Raju Pitta
```
#### quize think
``` python
#stack ADT
# input "18,19,29,15,16"
# output 15
stack =[]
stack.append(18)
stack.append(19)
stack.append(29)
stack.pop()
stack.pop()
stack.pop()
stack.append(15)
stack.append(16)
stack.pop()
print("out-put we need",stack)
stack.pop()
print("stack is empty :",stack)
```
```
```
## Queue
- A queue is an ordered list in which insertions (or called additions or pushes) and deletions (or called removals or pops) are made at different ends.
- New elements are inserted at rear end.
- Old elements are deleted at front end.
### Deque (Double Ended Queue)
Double Ended Queue is a type of queue in which insertion and removal of elements can be performed from either from the front or rear. Thus, it does not follow FIFO rule (First In First Out).
### Circular Queue:O(1)
#### Circular Queue Operations
The circular queue work as follows:
two pointers **FRONT** and **REAR**
```
<FRONT> track the first element of the queue
<REAR> track the last elements of the queue
initially, set value of <FRONT> and <REAR> to -1
```
1. Enqueue Operation
- check if the queue is full
- for the first element, set value of FRONT to 0
- circularly increase the **REAR** index by 1 (i.e. if the rear reaches the end, next it would be at the start of the queue)
- add the new element in the position pointed to by **REAR**
2. Dequeue Operation
- check if the queue is empty
- return the value pointed by **FRONT**
- circularly increase the **FRONT** index by 1
- for the last element, reset the values of **FRONT** and **REAR** to -1
However, the check for full queue has a new additional case:
```
Case 1: FRONT = 0 && REAR == SIZE - 1
Case 2: FRONT = REAR + 1
```
The second case happens when REAR starts from 0 due to circular increment and when its value is just 1 less than FRONT, the queue is full.
### Queue ADT
``` c++
template < class T >
class Queue // A finite ordered list
{
public:
// Constructor
Queue (int queueCapacity = 10);
// Check if the stack is empty
bool IsEmpty ( ) const;
// Return the front element
T& Front ( ) const;
// Return the rear element
T& Rear ( ) const;
// Insert a new element at rear
void Push (const T& item);
// Delete one element from front
void Pop ( );
private:
T* queue;
int front, rear; // init. value = -1
int capacity;
};
```
### Operation
``` c++
template < class T >
void Queue < T >::IsEmpty() const { return front==rear; }
template < class T >
T& Queue < T >::Front() const {
if(IsEmpty()) throw “Queue is empty!”;
return queue[(front+1)%capacity];
}
template < class T >
T& Queue < T >::Rear() const {
if(IsEmpty()) throw “Queue is empty!”;
return queue[rear];
}
```
### Push
``` C++
template < class T >
void Queue< T >::Push (const T& x)
{ // Add x at rear of queue
if((rear+1)%capacity == front)
{
// queue is going to full, double the capacity!
}
rear = (rear+1)%capacity;
queue [rear] = x;
}
```
### POP
``` C++
template < class T >
void Queue < T >::Pop ( )
{ // Delete front element from queue
if(IsEmpty()) throw “Queue is empty. Cannot delete.”;
front = (front+1)%capacity;
queue[front].~T(); // Delete the element
}
```
## 算數優先順序
### Infix (中序式): a+b > Postfix (後序式): ab+
###### Algorithm:
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, output it.
3. Else,
…..3.1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.
…..3.2 Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)
4. If the scanned character is an ‘(‘, push it to the stack.
5. If the scanned character is an ‘)’, pop the stack and and output it until a ‘(‘ is encountered, and discard both the parenthesis.
6. Repeat steps 2-6 until infix expression is scanned.
7. Print the output
8. Pop and output from the stack until it is not empty.
```python
class Conversion:
# Constructor to initialize the class variables
def __init__(self, capacity):
self.top = -1
self.capacity = capacity
# This array is used a stack
self.array = []
# Precedence setting
self.output = []
self.precedence = {'+':1, '-':1, '*':2, '/':2, '^':3}
# check if the stack is empty
def isEmpty(self):
return True if self.top == -1 else False
# Return the value of the top of the stack
def peek(self):
return self.array[-1]
# Pop the element from the stack
def pop(self):
if not self.isEmpty():
self.top -= 1
return self.array.pop()
else:
return "$"
# Push the element to the stack
def push(self, op):
self.top += 1
self.array.append(op)
# A utility function to check is the given character
# is operand
def isOperand(self, ch):
return ch.isalpha()
# Check if the precedence of operator is strictly
# less than top of stack or not
def notGreater(self, i):
try:
a = self.precedence[i]
b = self.precedence[self.peek()]
return True if a <= b else False
except KeyError:
return False
# The main function that converts given infix expression
# to postfix expression
def infixToPostfix(self, exp):
# Iterate over the expression for conversion
for i in exp:
# If the character is an operand,
# add it to output
if self.isOperand(i):
self.output.append(i)
# If the character is an '(', push it to stack
elif i == '(':
self.push(i)
# If the scanned character is an ')', pop and
# output from the stack until and '(' is found
elif i == ')':
while( (not self.isEmpty()) and self.peek() != '('):
a = self.pop()
self.output.append(a)
if (not self.isEmpty() and self.peek() != '('):
return -1
else:
self.pop()
# An operator is encountered
else:
while(not self.isEmpty() and self.notGreater(i)):
self.output.append(self.pop())
self.push(i)
# pop all the operator from the stack
while not self.isEmpty():
self.output.append(self.pop())
print "".join(self.output)
# Driver program to test above function
exp = "a+b*(c^d-e)^(f+g*h)-i"
obj = Conversion(len(exp))
obj.infixToPostfix(exp)
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
```
Google Drive
Gist
Clipboard
Sign in with Wallet
