voidpush(int x) { Node *currentNode = new Node; currentNode->value = x; currentNode->next = topNode; topNode = currentNode; if (isFirst) { min = x; isFirst = false; } if (x < min) { min = x; } }
voidpop() {
if (topNode->value == min)//如果栈顶数为最小值的处理方式 { Node *search = topNode; if (search->next != NULL)//注意这里的坑：如果是取最后一个结点，则清空栈 { min = search->next->value; } else { isFirst = true; } while (search->next != NULL) { search = search->next; if (search->value < min) { min = search->value; } } } topNode = topNode->next; }
inttop() { return topNode->value; }
intgetMin() { returnmin; } };
/** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */
classMyCircularQueue { public: vector<int> queue_data; int queueLength = 0; int queueSize = 0; int qFront = 0; int qEnd = 0; /** Initialize your data structure here. Set the size of the queue to be k. */ MyCircularQueue(int k) { queue_data.resize(k); queueSize = k; } /** Insert an element into the circular queue. Return true if the operation is successful. */ boolenQueue(int value) { if (queueLength >= queueSize) { returnfalse; } if (queueLength == 0) { queue_data[0] = value; qFront = 0; //这里是一个坑，如果队列初始化时为空队列，首位的位置要重新设置 qEnd = 0; } else { qEnd++; if (qEnd == queueSize) { qEnd = 0; } queue_data[qEnd] = value; } queueLength++; returntrue; }
/** Delete an element from the circular queue. Return true if the operation is successful. */ booldeQueue() { if (queueLength == 0) returnfalse; else { qFront++; if (qFront == queueSize) qFront = 0; } queueLength--; returntrue; }
/** Get the front item from the queue. */ intFront() { if (queueLength == 0) return-1; return queue_data[qFront]; }
/** Get the last item from the queue. */ intRear() { if (queueLength == 0) return-1; return queue_data[qEnd]; }
/** Checks whether the circular queue is empty or not. */ boolisEmpty() { if (queueLength == 0) returntrue; returnfalse; }
/** Checks whether the circular queue is full or not. */ boolisFull() { if (queueLength == queueSize) returntrue; returnfalse; } };
classMyLinkedList { public: Node *head, *next, *tail; int length;
/** Initialize your data structure here. */ MyLinkedList() { head = NULL; next = NULL; tail = NULL; length = 0; }
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */ intget(int index) { if (index < 0 || index >= length) return-1; else { Node *current = head; int returnVal = head->value; while (index-- >= 0) { returnVal = current->value; current = current->next; } return returnVal; } }
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */ voidaddAtHead(int val) { if (head == NULL) { Node *currentNode = new Node; head = currentNode; head->value = val; head->next = NULL; tail = head; length = 1; } else { Node *currentNode = new Node; (*currentNode).next = head; (*currentNode).value = val; head = currentNode; length++; } }
/** Append a node of value val to the last element of the linked list. */ voidaddAtTail(int val) { if (head == NULL) { Node *currentNode = new Node; head = currentNode; head->value = val; head->next = NULL; tail = head; length = 1; } else { Node *currentNode = new Node; (*currentNode).next = NULL; (*currentNode).value = val; (*tail).next = currentNode; tail = currentNode; length++; } }
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */ voidaddAtIndex(int index, int val) { Node *current = new Node; Node *insert = head; if (index < 0 || index > length) { return; } if (index == 0) { (*this).addAtHead(val); } else { if (index > length) return; if (index == length) { (*this).addAtTail(val); } else { while (index-- > 1) { insert = insert->next; } current->next = insert->next; current->value = val; insert->next = current; length++; } } }
/** Delete the index-th node in the linked list, if the index is valid. */ voiddeleteAtIndex(int index) { if (index < 0 || index >= length) return; if (index == 0) { head = head->next; length--; } else { Node *deleteNode = head; while (index-- > 1) { deleteNode = deleteNode->next; } deleteNode->next = deleteNode->next->next; if(deleteNode->next == NULL) { tail = deleteNode; } length--; } } };
/** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList* obj = new MyLinkedList(); * int param_1 = obj->get(index); * obj->addAtHead(val); * obj->addAtTail(val); * obj->addAtIndex(index,val); * obj->deleteAtIndex(index); */
STL中的链表
C++的STL包含了一个模板类:list.
这个模板类提供了一套完整的链表系统,这样你就不需要动手造轮子.
c++的list是由一个双向链表实现的.
下面是一些用法及实例:
1 2 3 4 5 6 7 8 9 10 11 12
list<int> my_list; //构造list(空的) //将数组赋值到list的示例: int myints[] = {75,23,65,42,13}; list<int> my_list(myints, myints+5); //给予list一个初始大小,但全部赋初值: std::list<int> sayings {20}; // A list of 20 empty int std::list<double> values(50, 3.14159265);//A List of 50 same elements //使用迭代器 my_list.begin();//返回首迭代器 my_list.end();//返回尾迭代器 my_list.rbegin();//返回反向的首迭代器,记住,c++的list是一个双向链表,所以你可以这么做. my_list.rend();//返回反向的尾迭代器