目录
225. 用队列实现栈
232. 用栈实现队列
387. 字符串中的第一个唯一字符
622. 设计循环队列
641. 设计循环双端队列
225. 用队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/
class MyStack{
private Queue<Integer> queue1;
private Queue<Integer> queue2;
//构造方法；
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
//压栈；
public void push(int x){
//两个队列为空，则选一个先入队列，这里选queue2；
//之后哪个队列非空，则入哪个队列；
if (!queue1.isEmpty()){
queue1.offer(x);
}else{
queue2.offer(x);
}
}
//出栈；
public int pop(){
//哪个队列非空，就将这个队列的元素转移到另一个队列；
//转移过程中，记录每一个出队列的元素；
//直到出元素的队列为空，不将该元素入队列，而是返回；
if(!queue1.isEmpty()){
int temp = queue1.poll();
while (!queue1.isEmpty()){
queue2.offer(temp);
temp = queue1.poll();
}
return temp;
}else if(!queue2.isEmpty()){
int temp = queue2.poll();
while (!queue2.isEmpty()){
queue1.offer(temp);
temp = queue2.poll();
}
return temp;
}
return -1;
}
//查看栈顶元素；
public int top(){
//哪个队列非空，就将这个队列的元素转移到另一个队列；
//转移过程中，记录每一个出队列的元素，直到出元素的队列为空，返回记录的元素；
int temp = -1;
if(!queue1.isEmpty()){
while(!queue1.isEmpty()){
temp = queue1.poll();
queue2.offer(temp);
}
}else if(!queue2.isEmpty()){
while(!queue2.isEmpty()){
temp = queue2.poll();
queue1.offer(temp);
}
}
return temp;
}
//判断栈是否为空；
public boolean empty(){
if(queue1.isEmpty() && queue2.isEmpty()){
return true;
}else {
return false;
}
}
}232. 用栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/
class MyQueue{
//两个栈；
private Stack<Integer> stack1 = null;
private Stack<Integer> stack2 = null;
//构造方法，初始化两个栈；
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
//压栈，stack1负责元素入队列；
public void push(int x){
stack1.push(x);
}
//stack2负责元素出队列；
public int pop(){
//如果stack2不为空，直接出；
if(!stack2.isEmpty()){
return stack2.pop();
}else {
//如果stack2为空，看看stack1是否为空；
//不为空将stack1元素转移到stack2，再将stack2栈顶元素出栈；
if(!stack1.isEmpty()){
while (!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
return -1;
}
//stack2的栈顶元素就是队列的队首元素；
public int peek(){
//如果stack2不为空，返回栈顶元素；
if(!stack2.isEmpty()){
return stack2.peek();
}else {
//如果stack2为空，看看stack1是否为空；
//不为空将stack1元素转移到stack2，再将stack2栈顶元素peek；
if(!stack1.isEmpty()){
while (!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.peek();
}
}
return -1;
}
public boolean empty(){
return stack1.isEmpty() && stack2.isEmpty();
}
}387. 字符串中的第一个唯一字符
https://leetcode.cn/problems/first-unique-character-in-a-string/
public int firstUniqChar1(String s) {
//创建一个代表26个英文字母的数组；
int[] arr = new int[26];
//将字符串s转换为字符数组；(也可以不转，使用String的方法即可)
char[] chs = s.toCharArray();
//将每个字符转换成整数，这个整数代表下标，放入arr数组中；
for(int i=0;i<chs.length;i++){
int n = chs[i] - 'a';
arr[n]++;
}
//遍历字符数组，查arr数组元素，找到第一个元素为1的，就返回这个字符；
for(int i=0;i<chs.length;i++){
int n = chs[i] - 'a';
if(arr[n] == 1){
return i;
}
}
//找不到返回-1；
return -1;
}622. 设计循环队列
https://leetcode.cn/problems/design-circular-queue/
class MyCircularQueue {
//用于存放元素的数组elem，队首下标front，队尾下标rear，队列有效元素size；
private int[] elem;
private int front;
private int rear;
private int size;
//构造方法，构造容量为k的数组；
public MyCircularQueue(int k) {
elem = new int[k];
}
//入队列方法；
public boolean enQueue(int value) {
if(this.isFull()){
return false;
}
//赋值给队尾元素，rear++；
elem[rear] = value;
rear++;
//超过最大容量，下标回到0；
if(rear >= elem.length){
rear = 0;
}
//有效元素++；
size++;
return true;
}
//出队列方法；
public boolean deQueue() {
if(this.isEmpty()){
return false;
}
//队首下标直接向后移动；
front++;
//超过最大容量，下标回到0；
if(front >= elem.length){
front = 0;
}
//有效元素--；
size--;
return true;
}
//查看队首元素；
public int Front() {
if(this.isEmpty()){
return -1;
}
return elem[front];
}
//查看队尾元素；
public int Rear() {
if(this.isEmpty()){
return -1;
}
//应注意队尾在每一次入队列后都会向后移动；
//因此想得到队尾元素需要查看队尾下标的前一个元素；
int temp = rear-1;
//处理循环队列中0下标的转换问题；
if(rear == 0){
temp = elem.length-1;
}
return elem[temp];
}
//有效元素为0，则队列为空；
public boolean isEmpty() {
return size == 0;
}
//有效元素等于数组容量，则队列满；
public boolean isFull() {
return size == elem.length;
}
}641. 设计循环双端队列
https://leetcode.cn/problems/design-circular-deque/
class MyCircularDeque {
//用于存放元素的数组，队首元素下标，队尾元素下标，有效元素个数；
private int[] elems;
private int front;
private int rear;
private int size;
//构造方法；
public MyCircularDeque(int k) {
elems = new int[k];
}
//头插法；
public boolean insertFront(int value) {
//判断是否已满；
if(this.isFull()){
return false;
}
//队首指针前移，注意转换最大下标和0下标；
if(front == 0){
front = elems.length-1;
}else{
front--;
}
//赋值和有效元素++；
elems[front] = value;
size++;
return true;
}
//尾插法；
public boolean insertLast(int value) {
//判断是否已满；
if(this.isFull()){
return false;
}
//赋值和有效元素++；
elems[rear] = value;
size++;
//队尾指针后移，注意转换最大下标和0下标；
if(rear == elems.length-1){
rear = 0;
}else{
rear++;
}
return true;
}
//头删法；
public boolean deleteFront() {
//判断是否为空；
if(this.isEmpty()){
return false;
}
//队首指针后移，注意转换最大下标和0下标；
if(front == elems.length-1){
front = 0;
}else{
front++;
}
//有效元素--；
size--;
return true;
}
//尾删法；
public boolean deleteLast() {
//判断是否为空；
if(this.isEmpty()){
return false;
}
//队尾指针前移，注意转换最大下标和0下标；
if(rear == 0){
rear = elems.length-1;
}else{
rear--;
}
//有效元素--；
size--;
return true;
}
//查看队首元素；
public int getFront() {
if(this.isEmpty()){
return -1;
}
return elems[front];
}
//查看队尾元素；
public int getRear() {
if(this.isEmpty()){
return -1;
}
//注意队尾元素应该是队尾指针的前一个，注意转换最大下标和0下标；
int temp = rear-1;
if(rear == 0){
temp = elems.length-1;
}
return elems[temp];
}
//判断是否为空；
public boolean isEmpty() {
return size == 0;
}
//判断是否已满；
public boolean isFull() {
return size == elems.length;
}
}
