栈
栈是一种线性的数据结构,遵循先进后出的原则,最后入栈的元素最先被去除,也就是说栈只能在栈顶进行插入和删除操作,而不能在栈中间或底部进行操作。
实现
#include <bits/stdc++.h>
using namespace std;
struct Stack
{
private:
int size;
int top;
int *arr;
public:
Stack(int size) : top(-1), size(size)
{
arr = new int[size];
}
bool IsEmpty()
{
return top == -1;
}
int Push(int val)
{
if (top + 1 == size)
{
// 自动扩容
int *temp = new int[size * 2];
copy(arr, arr + size, temp);
arr = temp;
size *= 2;
}
arr[++top] = val;
return val;
}
int Pop()
{
return arr[top--];
}
int Top()
{
if (top >= 0)
{
return arr[top];
}
else
{
return -1;
}
}
void Print()
{
for (int i = 0; i <= top; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
int GetSize()
{
return size;
}
int GetTop()
{
return top;
}
};
int main()
{
Stack *stack = new Stack(10);
for (int i = 0; i <= 20; i++)
{
stack->Push(i);
}
for (int i = 0; i <= 20; i++)
{
cout << stack->Pop() << " ";
}
}
队列
与栈类似,先进先出
实现
#include <bits/stdc++.h>
using namespace std;
struct Queue
{
private:
//最大容量
int size;
//头位置
int head;
//尾重要
int tail;
//元素数量
int count;
int *data;
public:
Queue(int n) : size(n), head(0), tail(0), count(0)
{
data = new int[n];
}
int push(int val)
{
if (count == size)
{
return 0;
}
data[tail++] = val;
if (tail == size)
tail = 0;
count++;
return 1;
};
int pop()
{
if (empty())
{
return 0;
}
head++;
count--;
return 1;
};
int front()
{
return data[head];
};
bool empty()
{
return count == 0;
};
void print()
{
cout << "count=" << count << endl;
if (count == 10)
{
}
int newt = tail - 1;
for (int i = 0; i < size; i++)
{
if (tail > head)
{
if (i >= head && i < tail)
{
cout << data[i] << " ";
}
else
{
cout << "o ";
}
}
else
{
if (i >= head || i < tail)
{
cout << data[i] << " ";
}
else
{
cout << "o ";
}
}
}
cout << endl;
for (int i = 0; i < size; i++)
{
if (i == head || i == tail - 1)
{
cout << "↑"
<< " ";
}
else
{
cout << " ";
}
}
cout << endl;
for (int i = 0; i < size; i++)
{
if (i == head && i == tail - 1)
{
cout << "h&t"
<< " ";
continue;
}
if (i == head)
{
cout << "h"
<< " ";
continue;
}
if (i == tail - 1)
{
cout << "t"
<< " ";
continue;
}
cout << " ";
}
cout << endl;
}
};
int main()
{
Queue *queue = new Queue(10);
queue->push(2);
queue->push(3);
queue->push(5);
queue->push(2);
queue->push(3);
queue->push(5);
queue->push(2);
queue->push(3);
queue->push(5);
queue->pop();
queue->pop();
queue->pop();
queue->push(2);
queue->push(3);
queue->push(5);
queue->pop();
queue->push(5);
// queue->push(5);
// queue->pop();
queue->pop();
queue->print();
return 0;
}
练习
leetcode p20 有效的括号
可以使用栈解决,如果是左括号则入栈,如果是右括号则匹配,匹配不上就返回false,最后栈不为空也是false.
import collections
class Solution:
def isValid(self, s: str) -> bool:
ss = collections.deque()
mapping = {")": "(", "}": "{", "]": "["}
for i in s:
if i in mapping.values():
ss.append(i)
elif i in mapping:
if not ss or ss.pop() != mapping[i]:
return False
return not ss
leetcode P225用队列实现栈
from collections import deque
class MyStack:
def __init__(self):
self.deque1 = deque()
def push(self, x: int) -> None:
self.deque1.appendleft(x)
for i in range(len(self.deque1)-1):
self.deque1.appendleft(self.deque1.pop())
def pop(self) -> int:
return self.deque1.pop()
def top(self) -> int:
return self.deque1[-1]
def empty(self) -> bool:
return len(self.deque1)==0